package sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class SelectionSort {

    public static void selectionSort(int[] arr){
        if(arr == null || arr.length <= 1){
            return;
        }
        int n = arr.length;
        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n; j++){
                if(arr[i] > arr[j]){
                    swap(arr, i, j);
                }
            }
        }
    }


    public static void selectionSortEnhance(int[] arr){
        if(arr == null || arr.length <= 1){
            return;
        }
        int n = arr.length;
        for(int i = 0; i < n-1; i++){
            int minIndex = i;       // 减少交换次数，每次选出 [i+1, n-1] 中最小的数 index，与 arr[i] 交换
            for(int j = i+1; j < n; j++){
                if(arr[minIndex] > arr[j]){
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    public static void swap(int[] arr, int i, int j){
        if( i == j){
            return;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
//        selectionSort(arr);
        selectionSortEnhance(arr);
        System.out.println(Arrays.stream(arr).boxed().collect(Collectors.toList()));
    }
}
